1. Field of the Invention
This invention pertains generally to the field of automated design techniques for electronic circuits, and more particularly to compaction and pitchmatching methods for hierarchically defined layouts of integrated circuits, and systems for implementing these methods.
2. Description of the Background Art
The complete design of an integrated circuit can be a very laborious and time-consuming process, and for many chips of practical interest the physical design of the electronic circuit is far too complex to be carried out without the aid of computers and sophisticated design tools. Since the advent of VLSI circuit technology this field of design automation has grown rapidly, and is becoming a mature technology in itself. There are now a variety of techniques available to aid the designer, and a substantial number of computer programs have been written to implement these techniques.
The physical design of an integrated circuit can be carried out in terms of the symbolic layout of the circuit, rather than the actual geometry of the masks and lavers that comprise the chip. The designer can thus work with transistors, wires, and other primitive components, and groups of these components termed "cells", represented by various symbols. The symbolic layout provides a higher level of abstraction than the mask layout, and is therefore easier for the designer to manipulate. The layout of these symbols can then be translated into a mask layout suitable for the actual fabrication of the chip. This translation requires additional technical information regarding the fabrication technology, which is stored in a "technology database" and used when the translation is carried out.
A symbolic layout that contains only primitive symbols--i.e. transistors, wires, capacitors and other physical components--is termed a "leaf cell". Many layouts contain a large number of groups of components that are substantially identical. Such a group may be used to define a cell, and the description of the layout may then be simplified by treating each such group as an instance of this cell. The cell has its own symbol; for example it may be represented as a rectangle with various ports for connecting wires or for abutment with ports of adjacent cells that are represented similarly. The components of the overall layout then may consist of cells, and the layout represents their relative placement and interconnection. By describing the layout in terms of cells rather than primitive symbols, again the designer's task is made much simpler.
Similarly, a given layout of cells may contain a large number of groups of cells, or cells and other components, in which the groups are identical. Such a group of cells may be used to define a "supercell", and the layout may again be simplified by treating each such group of cells as an instance of the supercell. Again, this supercell has its own symbol and ports, and the overall layout is a representation of the arrangement and interconnection of these supercells.
Obviously this process may be repeated, so that a symbolic layout can-be treated as a hierarchical structure with multiple levels. Each level is a symbolic layout of various cells and primitive components. Each such cell is in turn a symbolic layout of subcells and primitive components, and this layout defines the next lower level of the hierarchy. Since there may be more than one type of cell at any given level, the next lower level may contain several different branches. The cells at the lowest level are leaf cells since they contain no subcells, but only primitive components. Therefore the hierarchy can be visualized as an inverted "tree" with branches extending downward, and the lowest level depends on the branch in which it is located. In short, the leaf cells are located at the ends of the branches, and the trunk of the tree represents the symbolic layout of the whole chip, which is often termed the "root cell". This hierarchical description is a natural and concise representation for large designs.
The task of integrated circuit design generally includes optimization of one or more parameters of the circuit. The designer usually attempts to minimize the geometrical size of the overall structure. This minimization is subject to several constraints that ensure that the technical design rules are followed and the integrity of the circuit is maintained. For example certain components of the circuit must be separated by a minimum distance, and the connections between different components must be maintained. The automated process of size minimization is known as compaction. The compactor is a computer program that operates on a symbolic layout that constitutes the input data and produces a new symbolic layout. This new layout corresponds to the design of the minimum size circuit that preserves the integrity of the original circuit and complies with the design rule requirements.
Compaction of leaf cells is a process that has been studied extensively. Compaction techniques for leaf cells have been summarized in the article by David G. Boyer entitled "Symbolic Layout Compaction Review", given at the ACM IEEE 25th Design Automation Conference, 1988, paper 26.1. Some researchers have attempted to use leaf cell compactors on hierarchical symbolic layouts. For example, obviously one can "flatten" a given hierarchical layout into a leaf cell and then use a leaf cell compactor. This method would give a layout of absolute minimum size. However, such a brute force method has the drawback that the size of the database for the compacted output layout becomes enormous and the compaction process becomes prohibitively expensive even for layouts of moderate size. Furthermore the characterization and modification of the output layout is more difficult because the input hierarchy is lost in the compaction process.
Another approach to hierarchical compaction is the "bottom-up" technique, in which leaf cell compaction is applied level by level starting from the leaf cells and working upward. During compaction of each level of the hierarchy the cells and subcells are assumed to be rigid objects. Once a given level is compacted, the connectivity or port abutment between cells at the next higher level is generally destroyed and must be re-established before the next level can be compacted. This degradation of cell connectivity is a serious drawback in designs with cells that are largely connected by abutment.
A further approach is to de-couple the cell abutment and compaction problems. One simply fixes the port positions of leaf cells without taking into account the design constraints within these cells. One then applies a leaf cell compactor to these leaf cells with fixed port positions. A similar process is carried out at higher levels. This technique can lead to infeasible designs since the fixing of port positions may produce an over constrained compaction problem. Such a methodology is often a time-consuming trial and error process, and the resulting solution is usually sub-optimal.
A recent attack on the hierarchical compaction problem has been described in the paper by David Marpie entitled "A Hierarchy Preserving Hierarchical Compactor", published in ACM IEEE 27th Design Automation Conference, 1990, pp. 134-140. This technique simultaneously carries out leaf cell compaction and maintains the port connectivity between abutting cells, (termed "pitchmatching"), while preserving the hierarchical structure. In this method, the global compaction problem is formulated as a linear programming problem, which is solved by the "Revised Simplex Method". The number of variables and constraints that must be handled grows with the size of the hierarchy, and the computation time increases rapidly with the hierarchy size. Hence, the complexity of the overall method is significant and the size of the layout that can be dealt with is limited.
In short, the definition of hierarchical compaction in the truest sense is the minimizing of the area of the hierarchically defined symbolic layout while preserving the hierarchical structure, design rule compliance, and electrical connectivity between components and cells. For cells connected by abutment in the input layout, the connection must be maintained in the compacted layout; i.e. the compactor must include pitchmatching. The entire process must be handled globally; all constraints throughout the layout must be treated simultaneously. Prior to the present invention, no satisfactory techniques have been available for carrying out this compaction for large-sized layouts.